/**
 * LeetCode 206. 反转链表 - 递归解法详解
 * 
 * 问题描述：给你单链表的头节点 head，请你反转链表，并返回反转后的链表。
 * 
 * 递归思想核心：
 * 1. 递归的本质是"大问题分解为小问题"
 * 2. 反转链表 = 反转后面的子链表 + 调整当前节点的指向
 * 3. 递归的终止条件是到达链表末尾
 */

/**
 * 链表节点定义
 */
class ListNode {
    int val;
    ListNode next;
    
    ListNode() {}
    
    ListNode(int val) { 
        this.val = val; 
    }
    
    ListNode(int val, ListNode next) { 
        this.val = val; 
        this.next = next; 
    }
}

/**
 * 递归反转链表解决方案
 */
class ReverseLinkedListSolution {
    
    /**
     * 方法1：经典递归解法
     * 
     * 递归思路分析：
     * 1. 递归终止条件：head == null 或 head.next == null
     * 2. 递归过程：先递归反转后面的链表，再调整当前节点
     * 3. 返回值：反转后的新头节点
     * 
     * 时间复杂度：O(n) - 每个节点访问一次
     * 空间复杂度：O(n) - 递归调用栈的深度
     * 
     * @param head 原链表头节点
     * @return 反转后的链表头节点
     */
    public ListNode reverseList(ListNode head) {
        // 递归终止条件
        // 情况1：空链表
        // 情况2：只有一个节点的链表
        if (head == null || head.next == null) {
            return head;
        }
        
        // 递归反转后面的子链表
        // 假设原链表是：1 -> 2 -> 3 -> 4 -> 5
        // 当前head指向1，递归调用会返回反转后的：5 -> 4 -> 3 -> 2
        ListNode newHead = reverseList(head.next);
        
        // 关键步骤：调整指针方向
        // 此时 head = 1, head.next = 2
        // 我们需要让 2 指向 1，即 head.next.next = head
        head.next.next = head;
        
        // 断开原来的连接，避免形成环
        head.next = null;
        
        // 返回新的头节点
        return newHead;
    }
    
    /**
     * 方法2：带辅助参数的递归解法（尾递归优化思路）
     * 
     * 这种方法更容易理解递归过程
     * 
     * @param head 当前节点
     * @param prev 前一个节点
     * @return 反转后的链表头节点
     */
    public ListNode reverseListWithHelper(ListNode head) {
        return reverseHelper(head, null);
    }
    
    private ListNode reverseHelper(ListNode current, ListNode prev) {
        // 递归终止条件：到达链表末尾
        if (current == null) {
            return prev;  // prev就是新的头节点
        }
        
        // 保存下一个节点
        ListNode next = current.next;
        
        // 反转当前节点的指向
        current.next = prev;
        
        // 递归处理下一个节点
        return reverseHelper(next, current);
    }
    
    /**
     * 方法3：迭代解法（对比学习）
     * 
     * 虽然题目要求递归，但了解迭代解法有助于理解问题本质
     * 
     * @param head 原链表头节点
     * @return 反转后的链表头节点
     */
    public ListNode reverseListIterative(ListNode head) {
        ListNode prev = null;
        ListNode current = head;
        
        while (current != null) {
            ListNode next = current.next;  // 保存下一个节点
            current.next = prev;           // 反转指针
            prev = current;                // 移动prev
            current = next;                // 移动current
        }
        
        return prev;  // prev是新的头节点
    }
}

/**
 * 递归过程可视化演示类
 */
class RecursionVisualization {
    
    /**
     * 带调试信息的递归反转
     * 帮助理解递归调用过程
     */
    public ListNode reverseListWithDebug(ListNode head) {
        return reverseWithDebug(head, 0);
    }
    
    private ListNode reverseWithDebug(ListNode head, int depth) {
        // 打印递归深度和当前节点
        String indent = "  ".repeat(depth);
        System.out.println(indent + "递归调用 depth=" + depth + 
                          ", current=" + (head == null ? "null" : head.val));
        
        // 递归终止条件
        if (head == null || head.next == null) {
            System.out.println(indent + "到达递归底部，返回: " + 
                              (head == null ? "null" : head.val));
            return head;
        }
        
        // 递归调用
        System.out.println(indent + "递归处理子链表...");
        ListNode newHead = reverseWithDebug(head.next, depth + 1);
        
        // 反转操作
        System.out.println(indent + "执行反转: " + head.val + " -> " + head.next.val + 
                          " 变为 " + head.next.val + " -> " + head.val);
        head.next.next = head;
        head.next = null;
        
        System.out.println(indent + "返回新头节点: " + newHead.val);
        return newHead;
    }
}

/**
 * 测试和学习用例
 */
public class ReverseLinkedListRecursive {
    
    /**
     * 创建测试链表
     */
    public static ListNode createList(int[] values) {
        if (values.length == 0) return null;
        
        ListNode head = new ListNode(values[0]);
        ListNode current = head;
        
        for (int i = 1; i < values.length; i++) {
            current.next = new ListNode(values[i]);
            current = current.next;
        }
        
        return head;
    }
    
    /**
     * 打印链表
     */
    public static void printList(ListNode head) {
        if (head == null) {
            System.out.println("空链表");
            return;
        }
        
        ListNode current = head;
        while (current != null) {
            System.out.print(current.val);
            if (current.next != null) {
                System.out.print(" -> ");
            }
            current = current.next;
        }
        System.out.println();
    }
    
    public static void main(String[] args) {
        ReverseLinkedListSolution solution = new ReverseLinkedListSolution();
        RecursionVisualization visualization = new RecursionVisualization();
        
        System.out.println("=== LeetCode 206. 反转链表 - 递归解法演示 ===\n");
        
        // 测试用例1：正常链表
        System.out.println("测试用例1: [1,2,3,4,5]");
        int[] values1 = {1, 2, 3, 4, 5};
        ListNode head1 = createList(values1);
        
        System.out.print("原链表: ");
        printList(head1);
        
        System.out.println("\n--- 递归过程可视化 ---");
        ListNode reversed1 = visualization.reverseListWithDebug(head1);
        
        System.out.print("反转后: ");
        printList(reversed1);
        
        System.out.println("\n" + "=".repeat(50) + "\n");
        
        // 测试用例2：单个节点
        System.out.println("测试用例2: [1]");
        int[] values2 = {1};
        ListNode head2 = createList(values2);
        
        System.out.print("原链表: ");
        printList(head2);
        
        ListNode reversed2 = solution.reverseList(head2);
        System.out.print("反转后: ");
        printList(reversed2);
        
        System.out.println("\n" + "=".repeat(50) + "\n");
        
        // 测试用例3：空链表
        System.out.println("测试用例3: []");
        ListNode head3 = null;
        
        System.out.print("原链表: ");
        printList(head3);
        
        ListNode reversed3 = solution.reverseList(head3);
        System.out.print("反转后: ");
        printList(reversed3);
        
        System.out.println("\n=== 递归解法核心要点总结 ===");
        System.out.println("1. 递归终止条件：head == null || head.next == null");
        System.out.println("2. 递归调用：先处理子问题（反转后面的链表）");
        System.out.println("3. 处理当前层：调整当前节点的指针方向");
        System.out.println("4. 返回结果：返回反转后的新头节点");
        System.out.println("\n关键代码：");
        System.out.println("  head.next.next = head;  // 反转指针");
        System.out.println("  head.next = null;       // 断开原连接");
    }
}

/**
 * 递归思维训练题
 * 
 * 理解了反转链表的递归解法后，可以尝试这些相关问题：
 * 
 * 1. LeetCode 92. 反转链表 II（反转指定区间的链表）
 * 2. LeetCode 25. K 个一组翻转链表
 * 3. LeetCode 234. 回文链表（可以用递归检查）
 * 
 * 递归解题的通用思路：
 * 1. 找到递归终止条件（最小子问题）
 * 2. 找到递归关系（大问题如何分解为小问题）
 * 3. 确定递归函数的返回值和参数
 * 4. 处理当前层的逻辑
 */